package tree;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

public class InorderSuccessor_Offer053 {
    @Test
    public void test() {
        print(Arrays.asList(2,1,3), 1);
        print(Arrays.asList(5,3,8,2,4,null,null,1), 4);
        print(Arrays.asList(5,3,8,2,4,null,null,1), 8);
        print(Arrays.asList(5,3,8,2,4,null,null,1), 6);
        print(Arrays.asList(6,2,8,0,4,7,9,null,null,3,5), 2);
        print(Arrays.asList(6,2,8,0,4,7,9,null,null,3,5), 10);
        print(Arrays.asList(6,2,8,0,4,7,9,null,null,3,5), 1);
    }

    void print(List<Integer> list, int key) {
        TreeNode root = TreeNode.buildTree(list);
        TreeNode s = inorderSearchTargetOrSuccessor(root, key);
        TreeNode s2 = inorderSuccessorLooply(root, key);
        System.out.format("recursively: tree: %s, key: %s, successor: %s\n", list, key, s);
        System.out.format("looply: tree: %s, key: %s, successor: %s\n", list, key, s2);
    }

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode targetOrSuccessor = inorderSearchTargetOrSuccessor(root, p.val);
        if (targetOrSuccessor.val == p.val) {
            if (targetOrSuccessor.right != null) {
                return getMinNodeInRight(targetOrSuccessor);
            } else {
                return null;
            }
        }
        return targetOrSuccessor;
    }

    // root 后继 是 右子树的最左节点
    public TreeNode getMinNodeInRight(TreeNode root) {
        TreeNode minNode = root.right;
        while (minNode.left != null) {
            minNode = minNode.left;
        }
        return minNode;
    }

    public TreeNode inorderSearchTargetOrSuccessor(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            // 返回target本身, 待进一步找到successor
            return root;
        }
        if (val < root.val) {
            TreeNode targetOrSuccessor = inorderSearchTargetOrSuccessor(root.left, val);
            if (targetOrSuccessor == null) {
                return null;
            }
            if (targetOrSuccessor.val == val) {
                // 是target本身
                if (targetOrSuccessor.right != null) {
                    // target.right非null, 作为后继
                    return getMinNodeInRight(targetOrSuccessor);
                } else {
                    // target一定是root的左子树的最右节点
                    // 且root一定是最小的树, 因为它是第一个以根身份见到target在它的左子树上;
                    // 如果再小的话, target就不再左子树上了, 走下面的右子树了
                    return root;
                }
            } else {
                // 不是target本身, 说明已经是successor了, 直接返回
                return targetOrSuccessor;
            }
        } else {
            return inorderSearchTargetOrSuccessor(root.right, val);
        }
    }

    public TreeNode inorderSuccessorLooply(TreeNode root, int val) {
        TreeNode possibleSuccessor = null;
        TreeNode node = root;
        boolean found = false;
        while (node != null) {
            if (val < node.val) {
                // 遇到比它大, 就往左走, 同时记录下这个比它大的, 会越来越收敛
                possibleSuccessor = node;
                node = node.left;
            } else if (val == node.val){
                // 遇到相等, 标记一下, 还是往右走, 去找右子树的最小节点;
                // 下一个节点如果非null就一定比它大, 就是它的possibleSuccessor
                found = true;
                node = node.right;
            } else {
                // 遇到比它小, 就往右走, 但不更新possibleSuccessor
                node = node.right;
            }
        }
        return found ? possibleSuccessor : null;
    }
}
